using System;
using System.Collections.Generic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0114. 二叉树展开为链表")]
    public class No0114_Flatten : AbsBaseTestItem
    {
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        /*
        给定一个二叉树，原地将它展开为一个单链表。
        */

        public override void OnTest()
        {
            Action<int, string> action = (i, s) => { };
            var node = new TreeNode(1)
            {
                left = new TreeNode(2) { left = new TreeNode(3), right = new TreeNode(4), },
                right = new TreeNode(5) { right = new TreeNode(6) },
            };
            var result = new TreeNode(1)
            {
                right = new TreeNode(2)
                {
                    right = new TreeNode(3)
                    {
                        right = new TreeNode(4)
                        {
                            right = new TreeNode(5)
                            {
                                right = new TreeNode(6),
                            },
                        },
                    },
                },
            };
            Func<TreeNode, TreeNode> func = (node) =>
            {
                Flatten(node);
                return node;
            };
            Assert.TestExe(func, node, equalsMethod: (n1, n2) => n1.ToJSONString() == n2.ToJSONString(), result);
        }

        public void Flatten(TreeNode root)
        {
            TreeNode curr = root;
            while (curr != null)
            {
                if (curr.left != null)
                {
                    TreeNode next = curr.left;
                    TreeNode predecessor = next;
                    while (predecessor.right != null)
                    {
                        predecessor = predecessor.right;
                    }
                    predecessor.right = curr.right;
                    curr.left = null;
                    curr.right = next;
                }
                curr = curr.right;
            }
        }
    }
}
